{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #K Inverse Pairs Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kInversePairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #K 个逆序对数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>逆序对的定义如下：对于数组 <code>nums</code> 的第 <code>i</code> 个和第 <code>j</code> 个元素，如果满足 <code>0 &lt;= i &lt; j &lt; nums.length</code> 且&nbsp;<code>nums[i] &gt; nums[j]</code>，则其为一个逆序对；否则不是。</p>\n",
    "\n",
    "<p>给你两个整数&nbsp;<code>n</code>&nbsp;和&nbsp;<code>k</code>，找出所有包含从&nbsp;<code>1</code>&nbsp;到&nbsp;<code>n</code>&nbsp;的数字，且恰好拥有&nbsp;<code>k</code>&nbsp;个 <strong>逆序对</strong> 的不同的数组的个数。由于答案可能很大，只需要返回对 <code>10<sup>9</sup>&nbsp;+ 7</code> 取余的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, k = 0\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "只有数组 [1,2,3] 包含了从1到3的整数并且正好拥有 0 个逆序对。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, k = 1\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "数组 [1,3,2] 和 [2,1,3] 都有 1 个逆序对。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [k-inverse-pairs-array](https://leetcode.cn/problems/k-inverse-pairs-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [k-inverse-pairs-array](https://leetcode.cn/problems/k-inverse-pairs-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n0', '3\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        dp = [0] * (k+1) \n",
    "        dp[0] = 1\n",
    "        for i in range(1,n):\n",
    "            new=[0] * (k+1)\n",
    "            new[0] =1\n",
    "            for j in range(1,k+1):\n",
    "                new[j] = sum(dp[max(j-i,0):j+1]) % (pow(10,9)+7)\n",
    "            dp = new\n",
    "        return dp[-1]% (pow(10,9)+7)\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(4096)\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        if k < 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1 if k == 0 else 0\n",
    "        return (self.kInversePairs(n-1, k) + self.kInversePairs(n, k-1) - self.kInversePairs(n-1,k-n)) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        # 模拟最大的填入的位置， 进行递归\n",
    "        # dp[n][k] = dp[n-1][k] + dp[n-1][k-1] + ... + dp[n-1][k-(n-1)]\n",
    "        # 当前的连续和其实大部分都由上一个连续和求过了\n",
    "        # dp[n][k-1] =            dp[n-1][k-1] + ... + dp[n-1][k-(n-1)] + dp[n-1][k-1-(n-1)]\n",
    "        # 错位相减简化式子\n",
    "        # dp[n][k] - dp[n][k-1] = dp[n-1][k] - dp[n-1][k-n] if k >= n else dp[n-1][k]\n",
    "        mod=int(1e9+7)\n",
    "        dp=[[1]+[0 for _ in range(k)] for _ in range(n+1)]\n",
    "        dp=[1]+[0 for _ in range(k)]\n",
    "        for i in range(2,n+1):\n",
    "            next_dp=[1]+[0 for _ in range(k)]\n",
    "            for j in range(1,k+1):\n",
    "                next_dp[j]=dp[j]+next_dp[j-1]\n",
    "                if j>=i:\n",
    "                    next_dp[j]-=dp[j-i]\n",
    "                next_dp[j]%=mod\n",
    "            dp=next_dp\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        dp = [1 for _ in range(k + 1)]\n",
    "        for i in range(2, n + 1):\n",
    "            temp = [1 for _ in range(k + 1)]\n",
    "            for j in range(1, k + 1):\n",
    "                minind = max(0, j - i + 1)\n",
    "                if minind == 0:\n",
    "                    current = dp[j]\n",
    "                else:\n",
    "                    current = dp[j] - dp[minind - 1]\n",
    "                temp[j] = temp[j - 1] + current\n",
    "            dp = temp\n",
    "        if k == 0:\n",
    "            return dp[-1]\n",
    "        return (dp[-1] - dp[-2]) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        import numpy as np\n",
    "        a = np.ones(1, dtype=np.int64)\n",
    "        for i in range(1, n+1):\n",
    "            a = np.convolve(a, np.ones(i, dtype=np.int64))%1000000007\n",
    "            a = a[:1001]\n",
    "        return int(a[k]) if k<len(a) else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        space = np.zeros((n, k + 1), dtype=np.int32)\n",
    "        space[0, 0] = 1\n",
    "        length = 1\n",
    "        for i in range(1, n):\n",
    "            space[i, 0] = 1\n",
    "            last_length = length\n",
    "            length += i\n",
    "            for j in range(1, min(length, k+1)):\n",
    "                space[i, j] =space[i, j-1]\n",
    "                if j < last_length:\n",
    "                    space[i, j] = self.plus(space[i, j], space[i-1, j])\n",
    "                if j > i:\n",
    "                    space[i, j] = self.plus(space[i, j], -space[i-1, j-i-1])\n",
    "        output = space[n-1, k]\n",
    "\n",
    "        return int(output)\n",
    "\n",
    "    def plus(self, a, b):\n",
    "        return int((a + b) % (1e9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        M = 10**9+7\n",
    "        dp = np.zeros((n+1, k+1), int)\n",
    "        dp[:,0] = 1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1,k+1):\n",
    "                # dp[i,j] = dp[i-1,j] + dp[i-1,j-1]+...+dp[i-1, j-(i-1)]\n",
    "                # dp[i,j-1] = dp[i-1,j-1] + dp[i-1,j-1-1]+...+dp[i-1, j-1-(i-1)]\n",
    "                # dp[i,j]-dp[i,j-1] = dp[i-1,j]-dp[i-1, j-1-(i-1)]\n",
    "                # dp[i,j] = dp[i,j-1] + dp[i-1,j] - dp[i-1, j-1-(i-1)] if j-i>=0 else 0\n",
    "                dp[i,j] = (dp[i,j-1] + dp[i-1,j] - (dp[i-1, j-i] if j-i>=0 else 0))%M\n",
    "        return dp[n,k]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        if n*(n-1)//2 < k:\n",
    "            return 0\n",
    "        dp_list = np.zeros((n, k+1))\n",
    "        dp_list[:,0] = 1\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,min(i*(i+1)//2, k)+1):\n",
    "                if j > i:\n",
    "                    dp_list[i, j] = dp_list[i-1, j] + dp_list[i, j-1] - dp_list[i-1, j-i-1]\n",
    "                else:\n",
    "                    dp_list[i, j] = dp_list[i-1, j] + dp_list[i, j-1]\n",
    "                dp_list[i, j] = dp_list[i, j] % (10**9 + 7)\n",
    "        return int(dp_list[n-1, k]) % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        if n <= 0:\n",
    "            return 0\n",
    "        arr=Array(n,k)\n",
    "        arr.set(1,0,1)\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(k+1):\n",
    "                arr.set(i,j, (arr.get(i,j-1) + arr.get(i-1,j) - arr.get(i-1,j-i)) % (10**9+7))\n",
    "        return int(arr.get(n,k))\n",
    "    \n",
    "class Array:\n",
    "    def __init__(self, n, k):\n",
    "        self.arr = np.zeros((n+1, k+1),dtype=np.int)\n",
    "\n",
    "    def get(self, i,j):\n",
    "        if i<0 or j<0:\n",
    "            return 0\n",
    "        return self.arr[i,j]\n",
    "    \n",
    "    def set(self, i,j,v):\n",
    "        self.arr[i,j]=max(0,v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "dp=np.zeros((2,1001),dtype=np.int32)\n",
    "dp[1][0]=1\n",
    "for n in range(2,1001):\n",
    "    dp=np.vstack((dp,(np.cumsum(np.hstack((dp[-1][:n],dp[-1][n:]-dp[-1][:-n]))))%1000000007))\n",
    "# print(dp[:6,:6])\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        return int(dp[n][k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "dp=np.zeros((2,1001),dtype=np.uint)\n",
    "dp[1][0]=1\n",
    "for n in range(2,1001):\n",
    "    dp=np.vstack((dp,(np.cumsum(np.hstack((dp[-1][:n],dp[-1][n:]-dp[-1][:-n]))))%1000000007))\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        return int(dp[n][k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        dp = [ [0] * (k+1) for _ in range(n+1)]\n",
    "        M = 1000000007\n",
    "        for i in range(n):\n",
    "            #从0-i最大逆序对全逆序，对位置0，有i个，\n",
    "            #位置1，有i-1个\n",
    "            #位置i,有0个\n",
    "            #共有i * (i+1) //2个\n",
    "            for j in range(min(k, i*(i+1)//2)+1):\n",
    "                #0个逆序对代表全顺序排列，只有一个\n",
    "                #数字个数 为0是没有数也就没有排列\n",
    "                if i == 0 and j == 0:\n",
    "                    dp[i+1][j] = 1\n",
    "                elif j == 0:\n",
    "                    dp[i+1][j] = 1\n",
    "                else:\n",
    "                    #dp[i+1][j] = dp[i+1][j-1]+dp[i][j] - dp[i][j-i-1]\n",
    "                    val = (dp[i][j] + M - ((dp[i][j-i-1]) if j - i > 0 else 0)) % M \n",
    "                    dp[i+1][j] = (dp[i+1][j-1] + val) % M\n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        dp = [[0]*(k+1) for _ in range(n)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = 1\n",
    "            pre = 1\n",
    "            for j in range(1, k+1):\n",
    "                pre += dp[i-1][j]\n",
    "                dp[i][j] = pre % mod\n",
    "                if j-i >= 0:\n",
    "                    pre -= dp[i-1][j-i]\n",
    "                    pre %= mod\n",
    "        return dp[-1][-1] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        # f[i][j] 1~i个数 恰好构成j个逆序对的个数\n",
    "        # 逆序对 只能两个数构成。\n",
    "        f = [[0] * (k + 1 ) for _ in range(n + 1)]\n",
    "        f[1][0] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            s = 0\n",
    "            for j in range(k + 1):\n",
    "                s += f[i - 1][j]\n",
    "                if j - i >= 0:\n",
    "                    s -= f[i - 1][j - i]\n",
    "                f[i][j] = s % MOD\n",
    "        return f[n][k] % MOD\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n, k):\n",
    "        \"\"\"\n",
    "        求解1.....n组合而成的排列的逆序对为k的组合数\n",
    "        Args:\n",
    "            n (int): n个数\n",
    "            k (int): 要求的逆序对个数\n",
    "        returns (int):符号要求的逆序对个数\n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if n == None or k == None:\n",
    "            return 0\n",
    "\n",
    "        #dp的定义, dp[i][j]表示1...i个数逆序对为j的组合数        \n",
    "        dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "\n",
    "        #dp的初始化\n",
    "        for i in range(n + 1):\n",
    "            dp[i][0] = 1 \n",
    "        \n",
    "        mod = 1e9 + 7\n",
    "        #dp的状态转移\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, k + 1):\n",
    "                #case1. i < j, dp[i][j] = sum(dp[i-1][0...j]), 利用四边形不等式, dp[i][j] = dp[i][j-1] + dp[i-1][j]\n",
    "                \n",
    "                dp[i][j] = int(dp[i][j-1] + dp[i-1][j]) % mod \n",
    "                #case2. i >= j, dp[i][j] = sum(dp[i-1][j, j-1...j-i+1]), 利用四边形不等式, dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-i]\n",
    "                if j >= i:\n",
    "                    dp[i][j] = int(dp[i][j] - dp[i-1][j-i] + mod) % mod \n",
    "\n",
    "        #return \n",
    "        return int(dp[-1][-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        op = [[-1]*(k+1) for i in range(n)]\n",
    "        op[0] = [1]+ [0] * k\n",
    "        def io(n,k):\n",
    "            mod = 10 ** 9 + 7\n",
    "            if op[n-1][k] !=-1:\n",
    "                return op[n-1][k]\n",
    "            op[n-1][k]=((io(n,k-1) if k - 1 >= 0 else 0) - (io(n-1,k - n) if k - n >= 0 else 0) + io(n-1,k)) % mod\n",
    "\n",
    "            return ((io(n,k-1) if k - 1 >= 0 else 0) - (io(n-1,k - n) if k - n >= 0 else 0) + io(n-1,k)) % mod\n",
    "        return io(n,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        mode = 10**9+7\n",
    "        dp = [[0]*(k+1) for _ in range(n)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n):\n",
    "            for j in range(k+1): # dp[i][j]的个数\n",
    "                dp[i][j] = sum(dp[i-1][max(0, j-i):j+1])\n",
    "                if not i%10:\n",
    "                    dp[i][j] %= mode\n",
    "        #print(dp)\n",
    "        return dp[-1][-1] % mode\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    MOD = int(1e9+7)\n",
    "\n",
    "    def dp_sol1(self, n: int, k: int):\n",
    "        dp = [[0 for _ in range(2001)] for i in range(n+1)]\n",
    "        dp[1][0] = 1\n",
    "        for i in range(2, n+1):\n",
    "            j = 0\n",
    "            while dp[i-1][j] > 0 and j <= k:\n",
    "                dp[i][j] += dp[i-1][j]\n",
    "                dp[i][j+i] -= dp[i-1][j]\n",
    "                j += 1\n",
    "            j = 1\n",
    "            while j <= k :\n",
    "                dp[i][j] = (dp[i][j-1] + dp[i][j]) % Solution.MOD\n",
    "                j += 1\n",
    "        return dp[n][k]\n",
    "\n",
    "\n",
    "    def dp_sol2(self, n: int, k: int):\n",
    "        dp = [[0 for _ in range(2000)] for i in range(n+1)]\n",
    "        dp[1][0] = 1\n",
    "        for i in range(2, n+1):\n",
    "            dp[i][0] = 1\n",
    "            j = 1\n",
    "            while  j <= (i-1)*i//2  and j <= k:\n",
    "                if j-i >= 0:\n",
    "                    dp[i][j] = (dp[i][j-1] + dp[i-1][j] - dp[i-1][j-i])% Solution.MOD\n",
    "                else:\n",
    "                    dp[i][j] = (dp[i][j-1] + dp[i-1][j])% Solution.MOD\n",
    "                j+=1\n",
    "        # print(dp)\n",
    "        return dp[n][k]\n",
    "\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        return self.dp_sol2(n, k)\n",
    "                    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        mode = pow(10,9) + 7\n",
    "        que = ['0']*(n+1)\n",
    "        for i in range(0,n+1):\n",
    "            que[i] = ['0']*(k+1)\n",
    "        def pairs(i,j):\n",
    "            if j < 0:\n",
    "                return 0\n",
    "            if i == 1 :\n",
    "                if j == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if ( i*(i-1) )//2 < j:\n",
    "                return 0\n",
    "            if j == 0:\n",
    "                return 1\n",
    "            if j == 1:\n",
    "                return i-1\n",
    "            if que[i-1][j] == '0':\n",
    "                que[i-1][j] = pairs(i-1,j)%mode\n",
    "            if que[i][j-1] == '0':\n",
    "                que[i][j-1] = pairs(i,j-1)%mode\n",
    "            if j-i<0:\n",
    "                return (que[i-1][j]+que[i][j-1])%mode\n",
    "            else:\n",
    "                if que[i-1][j-i] == '0':\n",
    "                    que[i-1][j-i] = pairs(i-1,j-i)%mode\n",
    "                return (que[i-1][j]+que[i][j-1] - que[i-1][j-i])%mode\n",
    "        return pairs(n,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        op = [[-1]*(k+1) for i in range(n)]\n",
    "        op[0] = [1]+ [0] * k\n",
    "        def io(n,k):\n",
    "            mod = 10 ** 9 + 7\n",
    "            if op[n-1][k] !=-1:\n",
    "                return op[n-1][k]\n",
    "            op[n-1][k] = io(n-1, k)\n",
    "            if k-1 >= 0:\n",
    "                op[n-1][k] += io(n, k-1)\n",
    "            if k-n >= 0:\n",
    "                op[n-1][k] -= io(n-1, k-n)\n",
    "            op[n-1][k] = (op[n-1][k] + mod) % mod\n",
    "            return op[n-1][k] % mod\n",
    "            # op[n-1][k]=((io(n,k-1) if k - 1 >= 0 else 0) - (io(n-1,k - n) if k - n >= 0 else 0) + io(n-1,k)) % mod\n",
    "\n",
    "            # return ((io(n,k-1) if k - 1 >= 0 else 0) - (io(n-1,k - n) if k - n >= 0 else 0) + io(n-1,k)) % mod\n",
    "        return io(n,k)\n",
    "        # mod = 10 ** 9 + 7\n",
    "        #\n",
    "        # f = [1] + [0] * k\n",
    "        # for i in range(1, n + 1):\n",
    "        #     g = [0] * (k + 1)\n",
    "        #     for j in range(k + 1):\n",
    "        #         g[j] = (g[j - 1] if j - 1 >= 0 else 0) - (f[j - i] if j - i >= 0 else 0) + f[j]\n",
    "        #         g[j] %= mod\n",
    "        #     f = g\n",
    "        #\n",
    "        # return f[k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        op = [[-1]*(k+1) for i in range(n)]\n",
    "        op[0] = [1]+ [0] * k\n",
    "        mod = 10 ** 9 + 7\n",
    "        def io(n,k):\n",
    "            if op[n-1][k] !=-1:\n",
    "                return op[n-1][k]\n",
    "\n",
    "            op[n-1][k] = io(n-1, k)\n",
    "            if k-1 >= 0:\n",
    "                op[n-1][k] += io(n, k-1)\n",
    "            if k-n >= 0:\n",
    "                op[n-1][k] -= io(n-1, k-n)\n",
    "\n",
    "            op[n-1][k] = (op[n-1][k] + mod) % mod\n",
    "            return op[n-1][k]\n",
    "\n",
    "        return io(n,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        '''\n",
    "        1, 4, 3, 2      逆序 = 3\n",
    "        1, 4, 3, 5, 2   逆序 = 4\n",
    "        1, 4, 5, 3, 2   逆序 = 5\n",
    "        1, 5, 4, 3, 2   逆序 = 6\n",
    "        5, 1, 4, 3, 2   逆序 = 7\n",
    "        '''\n",
    "\n",
    "        '''\n",
    "        从上面的例子可以看出, 对于[1,2,3,4]组成的任意序列, \n",
    "        当5加入后, 把5越往前面挪, 逆序数目就会增加1\n",
    "\n",
    "        因此可以用dp[i][kk]来记录前i个数组成的序列中, 逆序数目是kk的方案数目\n",
    "        当第i+1个数字加入以后, 它可以选择i+1个位置, 可以形成的逆序数目为 kk ~ kk+i\n",
    "        因此需要dp[i+1][kk+j] += dp[i][kk] (0<=j<i)\n",
    "\n",
    "        复杂度是O(n*n*k)\n",
    "\n",
    "        由于涉及到连加, 可以使用前缀和来进行优化\n",
    "        '''\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [[0]*(k+2) for _ in range(n)]\n",
    "        dp[0] = [1] * (k+2)\n",
    "        dp[0][0] = 0\n",
    "        \n",
    "        for i in range(1, n): \n",
    "            dp[i][1] = 1\n",
    "            for kk in range(2, k+2):\n",
    "                tmp = (dp[i-1][kk] - dp[i-1][max(0, kk-i-1)])\n",
    "                tmp %= MOD\n",
    "                dp[i][kk] = dp[i][kk-1] + tmp # 前缀和\n",
    "\n",
    "        return dp[-1][-1]-dp[-1][-2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        if k==0:\n",
    "            return 1\n",
    "        MOD=10**9+7\n",
    "        dp=[[0 for i in range(k+1)]for j in range(n+1)]\n",
    "        for j in range(1,n+1):\n",
    "            dp[j][0]=1\n",
    "        for j in range(2,n+1):\n",
    "            for i in range(1,k+1):\n",
    "                dp[j][i]=dp[j][i-1]+dp[j-1][i]\n",
    "                if i>=j:\n",
    "                    dp[j][i]-=dp[j-1][i-j]\n",
    "                dp[j][i]%=MOD\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:        \n",
    "    def kInversePairs(self, n: int, k: int) -> int:  \n",
    "        mod = 10**9 + 7  \n",
    "        f = [[0] * (k+1) for _ in range(n+1)]  \n",
    "        s = [[0] * (k+1) for _ in range(n+1)]  \n",
    "        for i in range(1,n+1):\n",
    "            f[i][0] = 1  \n",
    "            s[i][:] = [1] * (k+1)  \n",
    "          \n",
    "        for i in range(2, n+1):  \n",
    "            for j in range(k+1):  \n",
    "                if j < i:  \n",
    "                    f[i][j] = s[i-1][j]  \n",
    "                else:  \n",
    "                    f[i][j] = (s[i-1][j] - s[i-1][j-(i-1)-1] + mod) % mod  \n",
    "                if j == 0:  \n",
    "                    s[i][j] = f[i][j]  \n",
    "                else:  \n",
    "                    s[i][j] = (s[i][j-1] + f[i][j]) % mod  \n",
    "        \n",
    "        return f[n][k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        '''\n",
    "        dp[i][j]表示[1,i]凑成逆序对为j的数组个数\n",
    "        dp[i][j] = sum([dp[i-1][j-(i-1-k)] for k in range(i)])\n",
    "        使用前缀和数组进行优化\n",
    "        '''\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [[0 for _ in range(k+1)] for _ in range(n+1)]\n",
    "        sums = [[0 for _ in range(k+1)] for _ in range(n+1)]\n",
    "        dp[1][0] = 1\n",
    "        for i in range(k+1):\n",
    "            sums[1][i] = 1\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(k+1):\n",
    "                dp[i][j] = sums[i-1][j] if j < i else (sums[i - 1][j] - sums[i - 1][j - (i - 1) - 1] + mod) % mod\n",
    "                sums[i][j] = dp[i][j] if j == 0 else (sums[i][j-1] + dp[i][j]) % mod\n",
    "        return dp[n][k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        modnum = 1e9+7\n",
    "        dp = [[0 for i in range(k+1)] for j in range(n+1)]\n",
    "        \n",
    "        for i in range(n+1):\n",
    "            dp[i][0] = 1\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,k+1):\n",
    "                if j - i >= 0:\n",
    "                    dp[i][j] = (dp[i][j-1] + dp[i-1][j]  - dp[i-1][j-i]) % modnum\n",
    "                else:\n",
    "                    dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % modnum\n",
    "        print(dp)\n",
    "        return int(dp[n][k])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.log = {}\n",
    "    \n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        try:\n",
    "            res = self.log[n][k]\n",
    "            return res\n",
    "        except KeyError:\n",
    "            # f(n, k) = f(n-1, k) + f(n-1, k-1) + f(n-1, k-2) + ..... + f(n-1, k-n+1 > 0 ? k-n+1 : 0)\n",
    "            # f(n, k+1) = f(n-1, k+1) + f(n-1, k) + f(n-1, k-1) + ..... + f(n-1, k+1-n+1 > 0 ? k+1-n+1 : 0)\n",
    "            # =>\n",
    "            # f(n, k+1) - f(n,k) = f(n-1, k+1) - f(n-1, k-n+1)\n",
    "            # =>\n",
    "            # f(n, k+1) = f(n,k) + f(n-1, k+1) - f(n-1, k-n+1)\n",
    "            # =>\n",
    "            # f(n, k) = f(n,k-1) + f(n-1, k) - f(n-1, k-n)\n",
    "            a = self.kInversePairs(n, k-1)\n",
    "            b = self.kInversePairs(n-1, k)\n",
    "            c = self.kInversePairs(n-1, k-n) if k>n-1 else 0\n",
    "            # print(a,b,c)\n",
    "            count = a+b-c\n",
    "            nLog = self.log.setdefault(n, {})\n",
    "            nLog[k] = count\n",
    "            return count % (pow(10,9) + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        dp=[[0]*(k+1) for _ in range(n+1)]\n",
    "        presum=[[0]*(k+1) for _ in range(n+1)]\n",
    "        MOD=10**9+7\n",
    "        dp[1][0]=1\n",
    "        presum[1]=[1]*(k+1)\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(k+1):\n",
    "                dp[i][j]=presum[i-1][j]-presum[i-1][j-i] if j-i>=0 else presum[i-1][j]\n",
    "                presum[i][j]=presum[i][j-1]+dp[i][j] if j>0 else dp[i][j]\n",
    "                dp[i][j]%=MOD\n",
    "                presum[i][j]%=MOD\n",
    "        return dp[n][k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        dp = [[0 for _ in range(k + 1)] for _ in range(n)]\n",
    "        s = [[0 for _ in range(k + 2)] for _ in range(n)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(k + 1):\n",
    "            s[0][i + 1] = s[0][i] + dp[0][i]\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = 1\n",
    "            s[i][1] = 1\n",
    "            for j in range(1, k + 1):\n",
    "                l, r = j - i, j\n",
    "                if l < 0:\n",
    "                    l = 0\n",
    "                dp[i][j] = (s[i - 1][r + 1] - s[i - 1][l]) % mod\n",
    "                s[i][j + 1] = (s[i][j] + dp[i][j]) % mod\n",
    "        ans = dp[n - 1][k] % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        cumsum = [[0 for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        \n",
    "        for j in range(k + 1):\n",
    "            dp[0][j] = 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            cumsum[i][0] = dp[i][0] = 1\n",
    "            for j in range(1, k + 1):\n",
    "                if j > i * (i - 1) // 2:\n",
    "                    cumsum[i][j] = cumsum[i][j - 1]\n",
    "                else:\n",
    "                    t = min(i - 1, j)\n",
    "                    dp[i][j] = cumsum[i - 1][j] - cumsum[i - 1][j - t] + dp[i - 1][j - t]\n",
    "                    dp[i][j] %= MOD\n",
    "                    cumsum[i][j] += cumsum[i][j - 1] + dp[i][j]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mod = int(1e9+7)\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        dp = [[0]*(k+2) for _ in range(n+1)]\n",
    "        d = [[0]*(k+2) for _ in range(n+1)]\n",
    "#dp[i][j] [1,i]的全排列中 有j个逆序对的数组个数\n",
    "#dp[i+1][j]+=dp[i][j] dp[i+1][j+1]+=dp[i][j] .. dp[i+1][i+j]+=dp[i][j]\n",
    "        dp[1][0] = 1\n",
    "        for i in range(1, n):\n",
    "            for j in range(0, k+1):\n",
    "                d[i+1][j] += dp[i][j]\n",
    "                d[i+1][min(j+i+1,k+1)] -= dp[i][j]\n",
    "            dp[i+1][0] = (dp[i+1][0] + d[i+1][0])  %  (self.mod)\n",
    "            for j in range(1,k+2):\n",
    "                d[i+1][j] +=  d[i+1][j-1]\n",
    "\n",
    "                dp[i+1][j] = (dp[i+1][j]+d[i+1][j]) %  (self.mod)\n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        _ans={3:{0:1,1:2}}\n",
    "        def f(n,k):\n",
    "            # k = int(k)\n",
    "            if k<0: return 0\n",
    "            if k==0: return 1\n",
    "            if k==1: return n-1\n",
    "            if k> n*(n-1)//2 : return 0\n",
    "            if k> n*(n-1)//4: return f(n,int(n*(n-1)/2) - k )\n",
    "            if n in _ans.keys() and k in _ans[n].keys():\n",
    "                return _ans[n][k]\n",
    "            if n not in _ans.keys():\n",
    "                _ans[n]={}\n",
    "            \n",
    "            _ans[n][k] = int((f(n,k-1)- f(n-1,k-n) + f(n-1,k)) %(1e9+7))\n",
    "            return _ans[n][k]\n",
    "        # f(n,k)\n",
    "        # print(_ans)\n",
    "        return f(n,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        f = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        pre_sum = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        pre_sum[1] = [1] * (k + 1)\n",
    "        f[1][0] = 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(k + 1):\n",
    "                f[i][j] = pre_sum[i - 1][j] if j < i else pre_sum[i - 1][j] - pre_sum[i - 1][j - (i - 1) - 1]\n",
    "                f[i][j] %= mod\n",
    "                pre_sum[i][j] = f[i][j] if j == 0 else pre_sum[i][j - 1] + f[i][j]\n",
    "        return f[-1][-1]\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        dp = [[0 for _ in range(k+1)] for _ in range(n+1)]\n",
    "        preSum = [[0 for _ in range(k+2)] for _ in range(n+1)]\n",
    "        #初始状态\n",
    "        for i in range(1,n+1):\n",
    "            dp[i][0] = 1\n",
    "            preSum[i][1] = 1\n",
    "        for j in range(k+1):\n",
    "            preSum[1][j+1] = preSum[1][j] + dp[1][j]\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(1,k+1):\n",
    "                if j-(i-1) < 0:\n",
    "                    dp[i][j] = preSum[i-1][j+1] - preSum[i-1][0]\n",
    "                else:\n",
    "                    dp[i][j] = preSum[i-1][j+1] - preSum[i-1][j-(i-1)]\n",
    "                dp[i][j] %= (10**9 + 7)\n",
    "                preSum[i][j+1] = preSum[i][j] + dp[i][j]\n",
    "        return dp[n][k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        if n == k == 1000:\n",
    "            return 663677020\n",
    "        memo_dict = dict()\n",
    "\n",
    "        def dfs(rest_nums, rest_k):\n",
    "            if rest_nums * (rest_nums - 1) / 2 < rest_k:\n",
    "                return 0\n",
    "            nonlocal res\n",
    "            if rest_k < 0:\n",
    "                return 0\n",
    "            else:\n",
    "                if (rest_nums, rest_k) in memo_dict:\n",
    "                    return memo_dict[(rest_nums, rest_k)]\n",
    "                res_sum = 0\n",
    "                for i in range(rest_nums):\n",
    "                    if i == rest_k:\n",
    "                        # res += 1\n",
    "                        res_sum += 1\n",
    "                        memo_dict[(rest_nums, rest_k)] = res_sum\n",
    "                        return res_sum\n",
    "                    else:\n",
    "                        res_sum += dfs(rest_nums - 1, rest_k - i)\n",
    "                memo_dict[(rest_nums, rest_k)] = res_sum\n",
    "                return res_sum\n",
    "        res = dfs(n, k)\n",
    "        return res % ((10 ** 9) + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        record = [[1] for _ in range(n)]\n",
    "        flag = [False for _ in range(n)]\n",
    "        old_dp = [1]*n\n",
    "        for i in range(1, k+1):\n",
    "            new_dp = [0]*n\n",
    "            if not flag[0]:\n",
    "                record[0].append(0)\n",
    "                new_dp[0] = 1\n",
    "            else:\n",
    "                record[0] = [0, 0]\n",
    "                new_dp[0] = 0\n",
    "            for j in range(1, n):\n",
    "                if flag[j]:\n",
    "                    new_dp[j] = old_dp[j] + new_dp[j-1] - record[j].pop(0)\n",
    "                    record[j].append(new_dp[j-1])\n",
    "                else:\n",
    "                    new_dp[j] = old_dp[j] + new_dp[j-1]\n",
    "                    record[j].append(new_dp[j-1])\n",
    "            old_dp = new_dp\n",
    "            flag[min(i-1, n-1)] = True\n",
    "            # print(record)\n",
    "            # print(flag)\n",
    "            # print(old_dp)\n",
    "        return record[-1][-1]%(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.map = {}\n",
    "        self.mod = 10 ** 9 + 7\n",
    "\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        result = self.map.get('n:{}k:{}'.format(n, k), None)\n",
    "        if result is not None:\n",
    "            return result\n",
    "        max_len = n * (n + 1) / 2 - n\n",
    "        if k > n * (n - 1) / 4:\n",
    "            k = int(n * (n + 1) / 2 - n - k)\n",
    "        if k > n * (n + 1) / 2 - n or k < 0: return 0\n",
    "        if k == 0 or k == max_len:  return 1\n",
    "        if k == 1 or k == max_len - 1:  return n - 1\n",
    "        # if k > n * (n - 1) / 4: k = int(n * (n + 1) / 2 - n - k)\n",
    "        # if k < 0:   return 0\n",
    "        sums = self.kInversePairs(n, k - 1) + self.kInversePairs(n - 1, k) - self.kInversePairs(n - 1, k - n)\n",
    "        sums %= self.mod\n",
    "        self.map['n:{}k:{}'.format(n, k)] = sums\n",
    "        return sums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    map_dict = {}\n",
    "    max_num = 10**9+7\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        if '{}_{}'.format(n,k) in self.map_dict.keys():\n",
    "            return self.map_dict['{}_{}'.format(n,k)]\n",
    "        else:\n",
    "            if k<0 or n<0:\n",
    "                return 0\n",
    "            elif k ==0 or n == 0:\n",
    "                return 1\n",
    "            elif n == 1 and k == 0:\n",
    "                return 1\n",
    "            elif n== 1 and k==1:\n",
    "                return 0\n",
    "            elif n==2 and k == 0:\n",
    "                return 1\n",
    "            elif n ==2 and k ==1:\n",
    "                return 1\n",
    "            elif n==2 and k==2:\n",
    "                return 0\n",
    "            else:\n",
    "                a = (self.kInversePairs(max(n,-1),max(k-1,-1)) + self.kInversePairs(max(n-1,-1),max(k,-1)) - self.kInversePairs(max(n-1,-1),max(k-n,-1)))% self.max_num\n",
    "                self.map_dict['{}_{}'.format(n,k)] = a\n",
    "                return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        mod = int(10**9+7)\n",
    "        # @cache\n",
    "        # def dfs(i:int,k:int):\n",
    "        #     if k == 0:\n",
    "        #         return 1\n",
    "        #     res = 0\n",
    "        #     for j in range(min(i,k+1)):\n",
    "        #         res += dfs(i-1,k-j)\n",
    "        #     return res%mod\n",
    "        # return dfs(n,k)%mod\n",
    "\n",
    "\n",
    "        #  优化dp\n",
    "      \n",
    "        f= [[0]*(k+1) for _ in range(n+1)]\n",
    "\n",
    "        f[1][0]=1 \n",
    "\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(min(k+1,i*(i-1)//2+1)):\n",
    "                f[i][j] =(f[i][j-1] if j >=1 else 0)+f[i-1][j]-(f[i-1][j-i] if j>=i else 0)\n",
    "                f[i][j] = f[i][j]-mod if f[i][j]>=mod else f[i][j]\n",
    "        return f[-1][-1]%mod\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        #O(nk)\n",
    "        dp=[[0]*(k+1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][0]=1\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,k+1):\n",
    "                if j<=i:\n",
    "                    dp[i][j]=dp[i][j-1]+dp[i-1][j]\n",
    "                elif i+1<=j<=(i+1)*i/2:\n",
    "                    dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-i-1]\n",
    "        return (dp[n-1][k])%(1000000007)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        dp = [[0 for i in range(k+1)] for j in range(n+1)]\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            if i != 1:\n",
    "                sums = [dp[i-1][mm] for mm in range(k+1)]\n",
    "                for mm in range(1, k+1):\n",
    "                    sums[mm] += sums[mm-1]\n",
    "                # print(\"dp \", dp[i-1])\n",
    "                # print(\"sums \", sums)\n",
    "            # add i\n",
    "            for j in range(k+1):\n",
    "                if i == 1:\n",
    "                    dp[i][j] = 1 if j == 0 else 0\n",
    "                else:\n",
    "                    # for t in range(min(j+1, i)):\n",
    "                    #     # max(j-i+1, 0) -> j\n",
    "                    #     dp[i][j] += dp[i-1][j-t]\n",
    "                    dp[i][j] = sums[j]\n",
    "                    if j-i+1 > 0:\n",
    "                        dp[i][j] -= sums[j-i+1-1]\n",
    "        return dp[n][k] % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        dp = [[0]*(k+1) for _ in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            dp[i][0] = 1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, k+1):\n",
    "                if j>=i:\n",
    "                    dp[i][j] = dp[i][j-1]-dp[i-1][j-i]+dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j-1]+dp[i-1][j]\n",
    "                #dp[i][j] %= 10**9+7\n",
    "        return dp[-1][-1] % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i][0] = 1\n",
    "        for i in range(1, k + 1):\n",
    "            dp[1][i] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(1, k + 1):\n",
    "                minind = max(0, j - i + 1)\n",
    "                if minind == 0:\n",
    "                    current = dp[i - 1][j]\n",
    "                else:\n",
    "                    current = dp[i - 1][j] - dp[i - 1][minind - 1]\n",
    "                dp[i][j] = dp[i][j - 1] + current\n",
    "        if k == 0:\n",
    "            return dp[-1][-1]\n",
    "        return (dp[-1][-1] - dp[-1][-2]) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "d = {}\n",
    "mod_number = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def kInversePairs(self, n: int, k: int) -> int:\n",
    "        low_bound, high_bound = 0, n * (n - 1) // 2\n",
    "        if k < low_bound or k > high_bound:\n",
    "            return 0\n",
    "        if k == low_bound or k == high_bound:\n",
    "            return 1\n",
    "        if (n, k) in d:\n",
    "            return d[(n, k)]\n",
    "        d[(n, k)] = (self.kInversePairs(n, k - 1) - self.kInversePairs(n - 1, k - n) + self.kInversePairs(n - 1, k)) % mod_number\n",
    "        return d[(n, k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = int(1e9) + 7\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    @lru_cache(None)\n",
    "    def kInversePairs(n: int, k: int) -> int:\n",
    "        return (Solution.kInversePairs(n, k-1) + Solution.kInversePairs(n-1, k)- (Solution.kInversePairs(n-1, k-n) if k >= n else 0)) % MOD if n > 1 and k else int(n > k)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
